package com.dylon.sort;

import java.util.Arrays;

/**
 * 快速排序
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] a = new int[]{2,5,3,1,4};
        System.out.println(Arrays.toString(a));
        sort(a,0 ,a.length-1);
        System.out.println(Arrays.toString(a));
    }


    public static void sort(int[] a,int left,int right) {
        int low=left;
        int high=right;
        // 下面两句的顺序一定不能混，否则会产生数组越界！！！
        if (low>high) // 作为判断是否截止条件
            return;
        int k = a[low]; // 额外空间k，取最左侧的一个作为衡量，最后要求左侧都比它小，右侧都比它大。
        while(low < high) { //这一轮要求把左侧小于a[low],右侧大于a[low]。
            while(low < high && a[high] >= k) { // 右侧找到第一个小于k的停止
                high--;
            }
            // 这样就找到第一个比它小的了
            a[low] = a[high]; // 放到low位置
            while(low < high && a[low] <= k) { // 在low往右找到第一个大于k的，放到右侧a[high]位置
                low++;
            }
            a[high] = a[low];
        }
        a[low] = k; // 赋值然后左右递归分治求之
        sort(a, left, low-1);
        sort(a, low+1, right);
    }

    /*
    快速排序是采用递归分治的方法进行求解，是一种不稳定排序,
    时间复杂度最坏是O(n^2),平均时间复杂度为O(nlogn),最好情况的时间复杂度为O(nlogn)。

    具体思想为：
        快排需要将序列变成两个部分，就是「序列左边全部小于一个数」，「序列右面全部大于一个数」，
            然后利用递归的思想再将左序列当成一个完整的序列再进行排序，同样把序列的右侧也当成一个完整的序列进行排序。
        其中这个数在这个序列中是可以随机取的，可以取最左边，可以取最右边，当然也可以取随机数。
            但是「通常」不优化情况我们取最左边的那个数。

      a=[2,5,3,1,4]    l=0,h=4, low=0,high=4 ,k=a[low]:2
                       a[h]:4 >= k → h=3
                       a[h]:1 <= k → a[l]=a[h]:1
      a=[1,5,3,1,4]    l=0,h=3, k=2
                       a[l]:1 <= k → l=1
                       a[l]:5 >= k → a[h]=a[l]:5
      a=[1,5,3,5,4]    l=1,h=3, k=2
                       a[h]:5 >= k → h=2
                       a[h]:3 >= k → h=1
      a=[1,5,3,5,4]    l=1,h=1, k=2
                       l==h → a[l]=k:2
      a=[1,2,3,5,4]
      b=[1,2,3,5,4]    l=low,h=l-1 → 0, low=0,high=0 ,k=a[low]:1
      c=[1,2,3,5,4]    l=l+1 → 2,h=high, low=2,high=4 ,k=a[low]:3
     */

}
